public class test04 {
    class Solution {
        public int countSubstrings(String s) {
            //子字符串：要求连续
            char[] ch = s.toCharArray();
            boolean[][] dp = new boolean[ch.length][ch.length];
            int res = 0;

            for(int i = ch.length-1;i>=0;i--){
                for(int j = i;j<ch.length;j++){
                    if(ch[i]==ch[j]){
                        if(j-i<=2 || dp[i+1][j-1]){
                            res++;
                            dp[i][j] = true;
                        }
                    }
                }
            }
            return res;
        }
    }
}
